#include "linearList.h"
using namespace std;
//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}
//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}


sequenceList::sequenceList(const int &maxsize, const int &length, float list[])
{
    maxCapcity=maxsize;
    curNumberOfItem=length;
    myList=new float [maxCapcity];
    for(int i=0;i<curNumberOfItem;i++)
    {
        myList[i]=list[i];
    }
}

sequenceList::~sequenceList()
{
    delete[] myList;
}

bool sequenceList::addItem(const float &elem)
{
    if(curNumberOfItem+1>maxCapcity)
    {
        return false;
    }
    float* add=myList+curNumberOfItem;
    *add=elem;
    curNumberOfItem++;
    return true;
}

bool sequenceList::insertItem(const int& weizhi,const float& yuansu)//在某位置添加元素
{
    if (weizhi < 0 || weizhi > curNumberOfItem || curNumberOfItem >= maxCapcity) 
    {
        return false; 
    }// 插入位置不合理或已满

    //如果可以插入，开始移动元素以腾出位置
    for(int i=curNumberOfItem;i>weizhi;i--)
    {
        myList[i]=myList[i-1];
    }

    myList[weizhi]=yuansu;
    curNumberOfItem++;
    return true;
}

int sequenceList::deleteItem(const float &elem)
{
    int tag=-1;
    for(int i=0;i<curNumberOfItem;i++)
    {
        float* flag=myList+i;
        if(*flag==elem)
        {
            float* flag1;
            float* flag2;
            for(int j=i;j<curNumberOfItem-1;j++)
            {
                flag1=myList+j;
                flag2=myList+j+1;
                *flag1=*flag2;
            }
            *flag2=0;
            curNumberOfItem--;
            tag=i;
            break;
        }
    }
    return tag;
}

bool sequenceList::locate(const int &num, float &val)
{
    if(num>=curNumberOfItem)
    {
        return false;
    }
    float* flag=myList+num;
    val=*flag;
    return true;
}

int sequenceList::locate(const float &elem)
{
    float* flag;
    for(int i=0;i<curNumberOfItem;i++)
    {
        flag=myList+i;
        if(*flag==elem)
        {
            return i;
        }
    }
    return -1;
}

void sequenceList::reverse()
{
    int a=curNumberOfItem/2;
    float* flag1;
    float* flag2;
    for(int i=0;i<a;i++)
    {
        flag1=myList+i;
        flag2=myList+curNumberOfItem-1-i;
        float temp;
        temp=*flag2;
        *flag2=*flag1;
        *flag1=temp;
    }
}
/**/


listNode::listNode(float nodeData, listNode *succ)
{
    data=nodeData;
    next=succ;
}

listNode::~listNode()
{
}

linkList::linkList()
{
    firstNode=new listNode;
    lastNode=firstNode;
    listSize=0;
}
linkList::linkList(const int &length, float list[])
{
    if(length==0)
    {
        firstNode=new listNode;
        lastNode=firstNode;
    }
    else
    {
        firstNode=new listNode;
        listNode* last=new listNode;
        firstNode->next=last;
        for(int i=length-1;i>=0;i--)
        {
            listNode* temp;
            temp=new listNode;
            temp->next=firstNode->next;
            firstNode->next=temp;
            firstNode->next->data=list[i];
        }
        listSize=length;
        curNode=firstNode;
        while(curNode != last)
        {
            if(curNode->next == last)
                lastNode=curNode;
            curNode = curNode->next;
        }
        last=NULL;
        lastNode->next=NULL;
    }
    
}

linkList::~linkList()
{
    if(firstNode==lastNode)
    {
        delete firstNode;
    }
    else
    {
        while(firstNode->next!=lastNode)
        {
            listNode* temp;
            temp=new listNode;
            temp->next=firstNode->next;
            firstNode->next=temp->next->next;
            delete temp->next;
            delete temp;
        }
        delete lastNode;
        delete firstNode;
    }
    
}

bool linkList::headInsertItem(const float &elem)
{
    if(firstNode==lastNode)
    {
        listNode* temp=new listNode;
        temp->data=elem;
        lastNode=temp;
        firstNode->next=temp;
        listSize++;
        temp=NULL;
        return true;
    }
    else
    {
        listNode* temp1=new listNode;
        temp1->data=elem;
        temp1->next=firstNode->next;
        firstNode->next=temp1;
        listSize++;
        temp1=NULL;
    }
    return true;
}

bool linkList::tailInsertItem(const float &elem)
{
    listNode* temp=new listNode;
    lastNode->next=temp;
    lastNode=temp;
    temp->data=elem;
    listSize++;
    temp=NULL;
    return true;
}

int linkList::insertItem(const int &index, const float &elem)
{
    if(index>listSize)
    {
        return -1;
    }
    if(index==listSize)
    {
        listNode* temp=new listNode;
        lastNode->next=temp;
        lastNode=temp;
        temp->data=elem;
        listSize++;
        temp=NULL;
        return index;
    }
    curNode=firstNode;
    int i;
    for(i=0;i<index;i++)
    {
        curNode=curNode->next;
    }
    listNode* tag=new listNode;
    tag->next=curNode->next;
    tag->data=elem;
    curNode->next=tag;
    tag=NULL;
    listSize++;
    return index;
}

int linkList::deleteItem(const float &elem)
{
    int i;
    curNode=firstNode;
    for(i=0;i<listSize;i++)
    {
        if(curNode->next->data==elem)
        {
            if(curNode->next==lastNode)
            {
                lastNode=curNode;
                delete curNode->next;
                listSize--;
                return i;
            }
            else
            {
                listNode* temp=new listNode;
                temp->next=curNode->next;
                curNode->next=curNode->next->next;
                delete temp->next;
                delete temp;
                listSize--;
                return i;
            }
        }
        curNode=curNode->next;
    }
    return -1;
}

bool linkList::locate(const int &index, float &val)
{
    if(index>=listSize||index<0)
    {
        return false;
    }
    int i;
    curNode=firstNode;
    for(i=0;i<index;i++)
    {
        curNode=curNode->next;
    }
    val=curNode->data;
    return true;
}

int linkList::locate(const float &elem)
{
    int i;
    curNode=firstNode;
    for(i=0;i<listSize;i++)
    {
        if(curNode->next->data==elem)
        {
            return i;
        }
        curNode=curNode->next;
    }
    return -1;
}

void linkList::ascendingOrder()
{
    int i,j;
    
    for(i=listSize-2;i>=0;i--)
    {
        curNode=firstNode;
        for(j=0;j<=i;j++)
        {
            if(curNode->next->data>curNode->next->next->data)
            {
                listNode* temp=new listNode;
                temp->next=curNode->next->next;
                curNode->next->next=curNode->next->next->next;
                temp->next->next=curNode->next;
                curNode->next=temp->next;
                delete temp;
            }
            curNode=curNode->next;
        }
        if(lastNode->next!=NULL)
        {
            lastNode=lastNode->next;
        }
    }
}

void linkList::reverse()
{
    int i;
    curNode=firstNode->next;
    lastNode=curNode;
    for(i=0;i<listSize-1;i++)
    {
        listNode* temp=new listNode;
        temp->next=curNode->next;
        curNode->next=curNode->next->next;
        temp->next->next=firstNode->next;
        firstNode->next=temp->next;
        delete temp;
    }
}

void link(linkList&list1, linkList&list2)
{
    list1.lastNode->next=list2.firstNode->next;
    list1.lastNode=list2.lastNode;
    list1.listSize=list1.listSize+list2.listSize;
    list2.lastNode=list2.firstNode;
}
void merge(linkList&list1, linkList&list2)
{
    link(list1,list2);
    list1.ascendingOrder();
    list1.reverse();
}